We study sequential coding of Markov sources under an error propagationconstraint. An encoder sequentially compresses a sequence of vector-sourcesthat are spatially i.i.d. but temporally correlated according to a first-orderMarkov process. The channel erases up to B packets in a single burst, butreveals all other packets to the destination. The destination is required toreproduce all the source-vectors instantaneously and in a lossless manner,except those sequences that occur in an error propagation window of length B +W following the start of the erasure burst. We define the rate-recoveryfunction R(B, W) - the minimum achievable compression rate per source sample inthis framework - and develop upper and lower bounds on this function. Our upperbound is obtained using a random binning technique, whereas our lower bound isobtained by drawing connections to multi-terminal source coding. Our upper andlower bounds coincide, yielding R(B, W), in some special cases. More generally,both the upper and lower bounds equal the rate for predictive coding plus aterm that decreases as 1/(W+1), thus establishing a scaling behaviour of therate-recovery function. For a special class of semi-deterministic Markovsources we propose a new optimal coding scheme: prospicient coding. Anextension of this coding technique to Gaussian sources is also developed. Forthe class of symmetric Markov sources and memoryless encoders, we establish theoptimality of random binning. When the destination is required to reproduceeach source sequence with a fixed delay and when W = 0 we also establish theoptimality of binning.
展开▼
